package Leetcode.数组字符串;

/**
 * @ClassName 删掉一个元素以后全为1的最长子数组
 * @since: 2023/8/11 10:51
 * @auth: kirito
 * @description:
 * 给你一个二进制数组 nums ，你需要从中删掉一个元素。
 *
 * 请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。
 *
 * 如果不存在这样的子数组，请返回 0 。
 * 提示 1：
 *
 * 输入：nums = [1,1,0,1]
 * 输出：3
 * 解释：删掉位置 2 的数后，[1,1,1] 包含 3 个 1 。
 * 示例 2：
 *
 * 输入：nums = [0,1,1,1,0,1,1,0,1]
 * 输出：5
 * 解释：删掉位置 4 的数字后，[0,1,1,1,1,1,0,1] 的最长全 1 子数组为 [1,1,1,1,1] 。
 * 示例 3：
 *
 * 输入：nums = [1,1,1]
 * 输出：2
 * 解释：你必须要删除一个元素。
 *
 *
 **/
public class 删掉一个元素以后全为1的最长子数组 {
    //1.假设被删除的为i，可以枚举所有i前后的连续为1的数组，求和比较
    public static int longestSubarray2(int[] nums) {
        int n = nums.length;

        // 创建两个辅助数组，用于存储当前位置之前和之后的连续1的个数
        int[] pre = new int[n]; // 存储当前位置之前的连续1的个数
        int[] suf = new int[n]; // 存储当前位置之后的连续1的个数

        // 计算pre数组：遍历数组nums，计算当前位置之前的连续1的个数
        pre[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            pre[i] = nums[i] != 0 ? pre[i - 1] + 1 : 0; // 如果当前位置是1，则在之前的基础上加1，否则重置为0
        }

        // 计算suf数组：遍历数组nums，计算当前位置之后的连续1的个数
        suf[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            suf[i] = nums[i] != 0 ? suf[i + 1] + 1 : 0; // 如果当前位置是1，则在之后的基础上加1，否则重置为0
        }

        int ans = 0;
        // 遍历数组nums，计算去掉一个0后，剩余子数组中连续1的最大个数
        for (int i = 0; i < n; ++i) {
            int preSum = i == 0 ? 0 : pre[i - 1]; // 当前位置之前的连续1的个数
            int sufSum = i == n - 1 ? 0 : suf[i + 1]; // 当前位置之后的连续1的个数
            ans = Math.max(ans, preSum + sufSum); // 更新最大值
        }

        return ans; // 返回最大连续1的个数
    }



    public static int longestSubarray(int[] nums) {
        int n = nums.length;
        int res = 0, right = 0, left = 0, zeros = 0;
        while (right < n) {
            if (nums[right] == 0) {
                zeros++;
            }
            while (zeros > 1) {
                if (nums[left] == 0) {
                    zeros--;
                }
                left++;
            }
            res = Math.max(res, right-left+1);
            right++;
        }
        return res-1;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 0, 1};
        System.out.println(longestSubarray(nums));
    }
}
